﻿// #define HASH_COLLISION

using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;
using System.Text;

namespace Mindless
{
    using PieceIndexPair = KeyValuePair<Piece, int /*index*/>;

    /// <summary>
    /// A checkers board. Highly optimized to reduce memory usage.
    /// </summary>
    struct Board : IEquatable<Board>, IDoubleHash
    {
        /// <summary>
        /// Constructs a new, empty board with the given dimensions.
        /// </summary>
        public Board(int width, int height, Color currentPlayer)
        {
            this.config = new BitVector32();
            this.config[maskWidth] = width - 1;
            this.config[maskHeight] = height - 1;
            this.config[maskCurrentPlayer] = (int) currentPlayer;

            this.blackPawns = this.blackKings = this.whitePawns = this.whiteKings = new BitVector32();
        }

        /// <summary>
        /// Holds board dimensions and current player color.
        /// ........
        /// cc       = current player color
        ///   xxx    = width - 1
        ///      yyy = height - 1
        /// </summary>
        BitVector32 config;
        static BitVector32.Section maskHeight;
        static BitVector32.Section maskWidth;
        static BitVector32.Section maskCurrentPlayer;

        /// <summary>
        /// Create bitmasks for reading config variable.
        /// </summary>
        static Board()
        {
            maskHeight = BitVector32.CreateSection(7);
            maskWidth = BitVector32.CreateSection(7, maskHeight);
            maskCurrentPlayer = BitVector32.CreateSection(3, maskWidth);
        }

        /// <summary>
        /// The receiver's width.
        /// </summary>
        public int Width
        {
            get { return this.config[maskWidth] + 1; }
        }

        /// <summary>
        /// The receiver's height.
        /// </summary>
        public int Height
        {
            get { return this.config[maskHeight] + 1; }
        }

        /// <summary>
        /// Color of the player whose turn it is to move.
        /// </summary>
        public Color CurrentPlayer
        {
            get { return (Color) this.config[maskCurrentPlayer]; }
        }

        /// <summary>
        /// Changes the color of the receiver's current player from White to Black, or vice versa.
        /// </summary>
        void InvertCurrentPlayer()
        {
            this.config[maskCurrentPlayer] = (int) Piece.OppositeColor(this.CurrentPlayer);
        }

        /// <summary>
        /// Accesses the piece at the given location.
        /// </summary>
        public Piece this[int x, int y]
        {
            get { return this[new Location(x, y)]; }
            set { this[new Location(x, y)] = value; }
        }

        /// <summary>
        /// Accesses the piece at the given location.
        /// </summary>
        public Piece this[Location pt]
        {
            get { return this[this.AsIndex(pt)]; }
            set { this[this.AsIndex(pt)] = value; }
        }

        /// <summary>
        /// Accesses the piece at the given index.
        /// </summary>
        public Piece this[int i]
        {
            get
            {
                Piece piece;
                int mask = 1 << i;

                if (this.blackPawns[mask])
                    piece = Piece.BlackPawn;
                else if (this.blackKings[mask])
                    piece = Piece.BlackKing;
                else if (this.whitePawns[mask])
                    piece = Piece.WhitePawn;
                else if (this.whiteKings[mask])
                    piece = Piece.WhiteKing;
                else
                    piece = Piece.Null;

                return piece;
            }
            set
            {
                int mask = 1 << i;

                    // clear the specified space on the board
                this.blackPawns[mask] = this.blackKings[mask] = this.whitePawns[mask] = this.whiteKings[mask] = false;

                    // set the specified space on the board to the given piece
                switch (value.Color)
                {
                    case Color.Black:
                        switch (value.Type)
                        {
                            case PieceType.Pawn: this.blackPawns[mask] = true; break;
                            case PieceType.King: this.blackKings[mask] = true; break;
                        }
                        break;
                    case Color.White:
                        switch (value.Type)
                        {
                            case PieceType.Pawn: this.whitePawns[mask] = true; break;
                            case PieceType.King: this.whiteKings[mask] = true; break;
                        }
                        break;
                }
            }
        }

        /// <summary>
        /// 32 bit positions per piece type provides support for up to 8x8 board (one bit per playable space on the
        /// board).
        /// </summary>
        BitVector32 blackPawns, blackKings, whitePawns, whiteKings;

        /// <summary>
        /// Converts the given location to an index. Spaces are indexed starting with 0 at the bottom left, and
        /// increasing first to the right, then up the board. E.g. For a 5x3 board:
        /// 
        ///    5.6.7
        ///    .3.4.
        ///    0.1.2
        /// </summary>
        int AsIndex(Location pt)
        {
            Debug.Assert(this.IsValidX(pt.X));
            Debug.Assert(this.IsValidY(pt.Y));
            Debug.Assert((pt.X + pt.Y) % 2 == 0);

            int x = pt.X;
            int y = pt.Y;

            if ((this.Width % 2 == 0) && (y % 2 == 1))
                x -= 1;

            return ((this.Width * y) + x) / 2;
        }

        /// <summary>
        /// Converts the given space index to an (x,y) location. Origin is at the bottom left.
        /// </summary>
        Location AsLocation(int i)
        {
            i *= 2;

            int x = i % this.Width;
            int y = i / this.Width;

            if ((this.Width % 2 == 0) && (y % 2 == 1))
                x += 1;

            return new Location(x, y);
        }

        /// <summary>
        /// Adds the given value (which fits in the given number of bits) to the given hash.
        /// From Sedgewick and http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.
        /// </summary>
        static void Hash(int value, int size, ref int hash)
        {
                // use a long int to avoid overflow, since the "base" size can be up to 32
            long lhash = hash;

                // mod by a large prime, but less than 2**31 to keep the hash positive
            hash = (int) (((lhash << size) + value) % 1610612741);
        }

        /// <summary>
        /// Hash code for a board.
        /// </summary>
        public override int GetHashCode()
        {
                // this determines the number of meaningful (i.e. potentially non-zero) bits in each value
            int nIndexes = ((this.Width * this.Height) + 1) / 2;

            int hash = this.config.Data;
            Hash(this.blackPawns.Data, nIndexes, ref hash);
            Hash(this.blackKings.Data, nIndexes, ref hash);
            Hash(this.whitePawns.Data, nIndexes, ref hash);
            Hash(this.whiteKings.Data, nIndexes, ref hash);

            return hash;
        }

        public int GetHashCode2()
        {
            int hash = 1;
            foreach (PieceIndexPair pair in this.GetPieces())
                hash += pair.Value;

            return hash;
        }

        /// <summary>
        /// Answers the non-null pieces on the board (and their indexes).
        /// </summary>
        IEnumerable<PieceIndexPair> GetPieces()
        {
            int nIndexes = ((this.Width * this.Height) + 1) / 2;
            for (int i = 0; i < nIndexes; ++i)
            {
                int mask = (1 << i);
                if (this.blackPawns[mask])
                    yield return new PieceIndexPair(Piece.BlackPawn, i);
                else if (this.blackKings[mask])
                    yield return new PieceIndexPair(Piece.BlackKing, i);
                else if (this.whitePawns[mask])
                    yield return new PieceIndexPair(Piece.WhitePawn, i);
                else if (this.whiteKings[mask])
                    yield return new PieceIndexPair(Piece.WhiteKing, i);
            }
        }

        /// <summary>
        /// Indicates whether two boards are equal.
        /// </summary>
        public bool Equals(Board board)
        {
            bool result = (this.config.Data == board.config.Data)
                 && (this.blackPawns.Data == board.blackPawns.Data)
                 && (this.blackKings.Data == board.blackKings.Data)
                 && (this.whitePawns.Data == board.whitePawns.Data)
                 && (this.whiteKings.Data == board.whiteKings.Data);

#if DEBUG && HASH_COLLISION
            if (result)
                Debug.Assert(this.GetHashCode() == board.GetHashCode());
            else if (this.GetHashCode() == board.GetHashCode())
            {
                Debug.WriteLine("***");
                Debug.WriteLine("Hash collision:");
                Debug.WriteLine(this);
                Debug.WriteLine(Convert.ToString(this.GetHashCode(), 2));
                Debug.WriteLine(board);
                Debug.WriteLine(Convert.ToString(board.GetHashCode(), 2));
            }
#endif
            return result;
        }

        /// <summary>
        /// Indicates whether two boards are equal.
        /// </summary>
        public override bool Equals(object obj)
        {
            return this.Equals((Board) obj);   
        }

        /// <summary>
        /// Indicates whether two boards are equal.
        /// </summary>
        public static bool operator ==(Board a, Board b)
        {
            return a.Equals(b);
        }

        /// <summary>
        /// Indicates whether two boards are not equal.
        /// </summary>
        public static bool operator !=(Board a, Board b)
        {
            return !a.Equals(b);
        }

        /// <summary>
        /// Answers a single-character representation of the given piece at the given location.
        /// </summary>
        static char ToChar(Piece piece, int x, int y)
        {
            string s = null;
            switch (piece.Color)
            {
                case Color.Black: s = "?bB"; break;
                case Color.White: s = "?wW"; break;
                case Color.None: s = ((x + y) % 2 == 0) ? "+" : "."; break;
            }

            return s[(int) piece.Type];
        }

        /// <summary>
        /// Display string.
        /// </summary>
        public override string ToString()
        {
            return this.ToString(0);
        }

        /// <summary>
        /// Display string.
        /// </summary>
        public string ToString(int indent)
        {
            StringBuilder sb = new StringBuilder();
            for (int y = this.Height - 1; y >= 0; --y)
            {
                sb.Append(Program.Indent(indent));
                for (int x = 0; x < this.Width; ++x)
                {
                    Piece piece = Piece.Null;
                    if ((x + y) % 2 == 0)
                        piece = this[x, y];
                    sb.Append(ToChar(piece, x, y));
                }
                sb.AppendLine();
            }
            sb.AppendFormat("{0}{1} to move ({2})", Program.Indent(indent), this.CurrentPlayer, this.GetHashCode());

            return sb.ToString();
        }

        /// <summary>
        /// Legal left/right motions.
        /// </summary>
        static readonly int[] xDirections = new int[]
            {
                -1, 1                  // every piece can move left and right
            };

        /// <summary>
        /// Legal up/down motions.
        /// </summary>
        static readonly int[/*PieceType*/][] yDirections = new int[][]
            {
                null,
                new int[] {     1 },   // pawns move forward only
                new int[] { -1, 1 }    // kings may move backward also
            };

        /// <summary>
        /// Indicates whether the given location corresponds to an actual square on the receiver.
        /// </summary>
        bool IsValid(Location loc)
        {
            return IsValidX(loc.X) && IsValidY(loc.Y);
        }

        /// <summary>
        /// Indicates whether the given x-coord represents a valid column on the receiver.
        /// </summary>
        bool IsValidX(int x)
        {
            return (x >= 0) && (x < this.Width);
        }

        /// <summary>
        /// Indicates whether the given y-coord represents a valid row on the receiver.
        /// </summary>
        bool IsValidY(int y)
        {
            return (y >= 0) && (y < this.Height);
        }

        /// <summary>
        /// Answers the y-coord of the given color's promotion row.
        /// </summary>
        int PromotionY(Color color)
        {
            int result = -1;
            switch (color)
            {
                case Color.White: result = this.Height - 1; break;   // moving up
                case Color.Black: result = 0; break;                 // moving down
                default: Debug.Assert(false); break;
            }

            return result;
        }

        /// <summary>
        /// Copies the receiver, while moving a single piece to a new location.
        /// </summary>
        /// <param name="curLoc">The current location of the piece being moved.</param>
        /// <param name="victimLoc">The location of the opponent piece being jumped. Use (-1,-1) for null.</param>
        /// <param name="newLoc">The new location of the piece being moved.</param>
        Board Copy(Location curLoc, Location victimLoc, Location newLoc)
        {
                // make a new board of the same size
            Board board = new Board(this.Width, this.Height, this.CurrentPlayer);

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                    // victim does not get copied
                if (loc == victimLoc)
                    continue;

                    // given piece is copied to a new location, and possibly promoted
                if (loc == curLoc)
                {
                    if ((piece.Type == PieceType.Pawn) && (newLoc.Y == this.PromotionY(piece.Color)))
                        piece = new Piece(piece.Color, PieceType.King);
                    board[newLoc] = piece;
                }
                else
                    board[loc] = piece;
            }

            return board;
        }

        /// <summary>
        /// Reflects along central vertical axis. Only valid for boards with an odd number of columns.
        /// </summary>
        Board ReflectVertical()
        {
            Debug.Assert(this.Width % 2 == 1);

                // make a new board of the same size
            Board board = new Board(this.Width, this.Height, this.CurrentPlayer);

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                Location newLoc = new Location(this.Width - loc.X - 1, loc.Y);
                board[newLoc] = this[loc];
            }

            return board;
        }

        /// <summary>
        /// Reflects along central horizontal axis. Only valid for boards with an odd number of rows.
        /// </summary>
        Board ReflectHorizontal()
        {
            Debug.Assert(this.Height % 2 == 1);

            Board board = new Board(this.Width, this.Height, this.CurrentPlayer);

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                Location newLoc = new Location(loc.X, this.Height - loc.Y - 1);
                board[newLoc] = this[loc];
            }

            return board;
        }

        /// <summary>
        /// Reflects along diagonal axis from bottom-left to top-right. Only valid for square boards.
        /// </summary>
        Board ReflectDiagonal()
        {
            Debug.Assert(this.Width == this.Height);

                // make a new board of the same size
            Board board = new Board(this.Height, this.Width, this.CurrentPlayer);

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                Location newLoc = new Location(loc.Y, loc.X);
                board[newLoc] = this[loc];
            }

            return board;
        }

        /// <summary>
        /// Rotates 180 degrees. Only valid for boards where the sum of the number of rows and columns is even.
        /// This is a combination of ReflectHorizontal and ReflectVertical, and so is technically not really
        /// necessary. It is provided because the intermediate board is invalid for some boards (e.g. even square
        /// boards).
        /// </summary>
        Board Rotate180()
        {
            Debug.Assert((this.Width + this.Height) % 2 == 0);

                // make a new board of the same size
            Board board = new Board(this.Width, this.Height, this.CurrentPlayer);

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                Location newLoc = new Location(this.Width - loc.X - 1, this.Height - loc.Y - 1);
                board[newLoc] = this[loc];
            }

            return board;
        }

        /// <summary>
        /// Exchange piece colors and active player.
        /// </summary>
        Board Invert()
        {
                // make a new board of the same size
            Board board = new Board(this.Width, this.Height, this.CurrentPlayer);

                // opposite player is playing
            board.InvertCurrentPlayer();

                // copy each piece onto the new board
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Piece piece = piecePair.Key;
                Location loc = this.AsLocation(piecePair.Value);

                piece = new Piece(Piece.OppositeColor(piece.Color), piece.Type);
                board[loc] = piece;
            }

            return board;
        }

        /// <summary>
        /// Answers all possible variations of the receiver based on available symmetries.
        /// </summary>
        public IEnumerable<Board> GetVariations()
        {
                // are there any pawns on the board? if so, this limits applicable symmetries
            bool pawns = (this.blackPawns.Data != 0) || (this.whitePawns.Data != 0);

                // dimensions of the board determine applicable symmetries
            bool isSquare = (this.Width == this.Height);
            bool isOddX = (this.Width % 2 == 1);
            bool isOddY = (this.Height % 2 == 1);

                // specify a string that cycles through all available symmetries
                // had to work this part out on paper :)
            string sFunc =
                pawns
                    ? isOddX
                        ? isOddY
                            ? "_V+V"
                            : "_V"
                        : isOddY
                            ? "_*"
                            : "_+"
                    : isOddX
                        ? isOddY
                            ? "_HVHDVHV".Substring(0, isSquare ? 8 : 4)
                            : "_V"
                        : isOddY
                            ? "_H"
                            : "_RDR".Substring(0, isSquare ? 4 : 2);

                // apply the transformations, gathering each board produced
            Board board = this;
            foreach (char cFunc in sFunc)
            {
                switch (cFunc)
                {
                    case '_': Debug.Assert(board == this);
                        break;
                    case 'H': board = board.ReflectHorizontal();           // N(rows) is odd
                        break;
                    case 'V': board = board.ReflectVertical();             // N(cols) is odd
                        break;
                    case 'D': board = board.ReflectDiagonal();             // square: N(rows) = N(cols)
                        break;
                    case 'R': board = board.Rotate180();                   // N(rows) + N(cols) is even
                        break;
                    case '+': board = board.Rotate180().Invert();          // same as RI, but in a single step
                        break;
                    case '*': board = board.ReflectHorizontal().Invert();  // same as HI, but in a single step
                        break;
                }
                yield return board;

                    // inversions are explicitly specified in the pawn strings, but are implicitly applicable
                    // to every step of a non-pawn board
                if (!pawns)
                    yield return board.Invert();
            }
        }

        /// <summary>
        /// Creates the resulting boards for all legal jump moves for the piece at the given location
        /// and adds them to the given collection, answering the number added.
        /// </summary>
        IEnumerable<Board> GetLegalJumps(Location loc)
        {
            Piece piece = this[loc];
            Debug.Assert(piece.Color != Color.None);
            Debug.Assert(piece.Type != PieceType.None);

                // check all possible motions
            foreach (int dx in xDirections)
            {
                foreach (int dy in yDirections[(int) piece.Type])
                {
                        // black pieces move down the board, white pieces move up
                    Vector vec = new Vector(dx, dy * Piece.YDirection(piece.Color));

                        // location of the piece to be jumped over
                    Location victimLoc = loc + vec;

                        // given piece's landing spot
                    Location newLoc = victimLoc + vec;
                    if (this.IsValid(newLoc))
                    {
                        Piece victim = this[victimLoc];
                        Piece empty = this[newLoc];

                            // if we jumped over an opponent to an empty square, we have a legal jump
                        if ((empty == Piece.Null) && (victim != Piece.Null) && (victim.Color != piece.Color))
                        {
                                // jump the piece over the victim
                            Board board = this.Copy(loc, victimLoc, newLoc);

                                // further jumps possible for this piece?
                            bool hasFurther = false;
                            foreach (Board further in board.GetLegalJumps(newLoc))
                            {
                                hasFurther = true;
                                yield return further;
                            }
                                // end of the jump chain - opponent gets to play next
                            if (!hasFurther)
                            {
                                board.InvertCurrentPlayer();
                                yield return board;
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Creates the resulting boards for all legal "slide" moves (i.e. non-jumps) for the piece at the
        /// given location and adds them to the given collection, answering the number added.
        /// </summary>
        IEnumerable<Board> GetLegalSlides(Location loc)
        {
            Piece piece = this[loc];
            Debug.Assert(piece.Color != Color.None);
            Debug.Assert(piece.Type != PieceType.None);

                // check all possible motions
            foreach (int dx in xDirections)
            {
                foreach (int dy in yDirections[(int) piece.Type])
                {
                        // black pieces move down the board, white pieces move up
                    Vector vec = new Vector(dx, dy * Piece.YDirection(piece.Color));

                        // spot to which the given piece is sliding
                    Location newLoc = loc + vec;
                    if (this.IsValid(newLoc))
                    {
                        Piece empty = this[newLoc];
                        if (empty == Piece.Null)
                        {
                                // slide the piece to its new location
                            Board board = this.Copy(loc, Location.Null, newLoc);
                            board.InvertCurrentPlayer();
                            yield return board;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Answers a collection of the resulting boards for all legal moves for the current player.
        /// </summary>
        public IEnumerable<Board> GetLegalMoves()
        {
            bool hasJump = false;

                // examine each the current player's pieces
            foreach (PieceIndexPair piecePair in this.GetPieces())
            {
                Location loc = this.AsLocation(piecePair.Value);
                
                    // can it jump?
                if (this[loc].Color == this.CurrentPlayer)
                {
                    foreach (Board board in this.GetLegalJumps(loc))
                    {
                        hasJump = true;
                        yield return board;
                    }
                }
            }
                // only look for slides if there are no jumps
            if (!hasJump)
            {
                foreach (PieceIndexPair piecePair in this.GetPieces())
                {
                    Location loc = this.AsLocation(piecePair.Value);
                    
                        // can it slide?
                    if (this[loc].Color == this.CurrentPlayer)
                    {
                        foreach (Board board in this.GetLegalSlides(loc))
                            yield return board;
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            Board board = new Board(5, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            IDictionary<Board, object> variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(5, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 4, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 4, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(5, 4, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(5, 4, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 6, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(4, 6, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(3, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.Pawn);
            board[1, 3] = new Piece(Color.Black, PieceType.Pawn);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);

            Console.WriteLine();
            board = new Board(3, 5, Color.Black);
            board[0, 0] = new Piece(Color.White, PieceType.King);
            board[1, 3] = new Piece(Color.Black, PieceType.King);
            variations = new Dictionary<Board, object>();
            foreach (Board variation in board.GetVariations())
                variations[variation] = null;
            Console.WriteLine("{0} variations", variations.Count);
            foreach (Board variation in variations.Keys)
                Console.WriteLine(variation);
        }
    }
}
